﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace machines_lib
{
    /// <summary>
    /// Simple custom implementation of a Deque
    /// </summary>
    /// <typeparam name="T">The type of objects stored in the Deque</typeparam>
    public class Deque<T>: IEnumerable<T>
        where T: class
    {
        protected class DequeEnumerator : IEnumerator<T>
        {
            Deque<T>.Node beginNode;
            Deque<T>.Node currentNode;

            public DequeEnumerator(Deque<T> d)
            {
                beginNode = currentNode = d.Begin;
            }

            #region IEnumerator<T> Members

            public T Current
            {
                get
                {
                    try
                    {
                        return ((DataNode)currentNode).data;
                    }
                    catch (InvalidCastException ex)
                    {
                        throw new InvalidOperationException("It appears that this iterator instance refers to a dataless node", ex);
                    }
                }
            }

            #endregion

            #region IDisposable Members

            /// <summary>
            /// Why, oh why, must I implement this method?
            /// </summary>
            public void Dispose()
            {
            }

            #endregion

            #region IEnumerator Members

            object System.Collections.IEnumerator.Current
            {
                get { return Current; }
            }

            public bool MoveNext()
            {
                currentNode = currentNode.next;
                return ((currentNode as DataNode) != null);
            }

            public void Reset()
            {
                currentNode = beginNode;
            }

            #endregion
        }

        private Node begin, end;

        public Deque()
        {
            begin = new Node();
            end = new Node();
            begin.next = end;
            end.prev = begin;
        }

        /// <summary>
        /// Check if the deque is empty
        /// </summary>
        /// <returns>true if deque is empty; false otherwise</returns>
        public bool IsEmpty()
        {
            return (begin.next == end);
        }

        /// <summary>
        /// Retrieve & remove the element at the back of the deque
        /// </summary>
        /// <returns>The element which was removed from the back of the deque</returns>
        /// <exception cref="System.InvalidOperationException">The deque is empty</exception>
        public T Pop_Back()
        {
            if (IsEmpty())
                throw new InvalidOperationException("Attempted to call Pop_Back() on an empty deque");

            DataNode result = (DataNode)(end.prev);
            end.prev = result.prev;
            return result.data;
        }

        /// <summary>
        /// Retrieve & remove the element at the back of the deque
        /// </summary>
        /// <returns>The element which was removed from the back of the deque</returns>
        /// <exception cref="System.InvalidOperationException">The deque is empty</exception>
        public T Pop_Front()
        {
            if (IsEmpty())
                throw new InvalidOperationException("Attempted to call Pop_Back() on an empty deque");

            DataNode result = (DataNode)(begin.next);
            begin.next = result.next;
            return result.data;
        }

        /// <summary>
        /// Retrieve the element at the back of the deque, without removing it.
        /// </summary>
        /// <returns>The element at the back of the deque, or null if the deque is empty</returns>
        public T Peek_Back()
        {
            if (IsEmpty())
                return null;
            else
                return ((DataNode)(end.prev)).data;
        }

        /// <summary>
        /// Retrieve the element at the front of the deque, without removing it.
        /// </summary>
        /// <returns>The element at the front of the deque, or null if the deque is empty</returns>
        public T Peek_Front()
        {
            if (IsEmpty())
                return null;
            else
                return ((DataNode)(begin.next)).data;
        }

        /// <summary>
        /// Insert an element at the front of the deque
        /// </summary>
        /// <param name="elem">The element to insert</param>
        public void Push_Front(T elem)
        {
            begin.next = new DataNode(elem, begin.next, null);
        }

        /// <summary>
        /// Insert an element at the back of the deque
        /// </summary>
        /// <param name="elem">The element to insert</param>
        public void Push_Back(T elem)
        {
            end.prev = new DataNode(elem, null, end.prev);
        }

        protected Node Begin
        {
            get { return begin; }
        }

        protected Node End
        {
            get { return end; }
        }

        /// <summary>
        /// Represents a doubly-linked node which contains data within a Deque
        /// </summary>
        protected class DataNode: Node
        {
            public T data;

            public DataNode(T _data)
                : base()
            {
                data = _data;
            }

            public DataNode(T _data, Node nextNode, Node previousNode)
                : base(nextNode, previousNode)
            {
                data = _data;
            }
        }

        /// <summary>
        /// Represents a doubly-linked node within a deque
        /// </summary>
        protected class Node
        {
            public Node next;
            public Node prev;

            public Node()
            {
                next = prev = null;
            }

            public Node(Node nextNode, Node previousNode)
            {
                next = nextNode;
                prev = previousNode;
            }
        }

        #region IEnumerable<T> Members

        public IEnumerator<T> GetEnumerator()
        {
            throw new NotImplementedException();
        }

        #endregion

        #region IEnumerable Members

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            throw new NotImplementedException();
        }

        #endregion
    }
}
